package leetcode;
/**
 * 剑指OfferⅡ 021.删除链表的倒数第N个节点
 * 给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 */
public class Offer_021 {
    //快慢指针法
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //特殊情况：当head为空
        if(head == null){
            return head;
        }
        //遇到删除问题，就建一个虚拟头节点
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        //初始位置都在dummyHead处，依然让fast先走n步
        ListNode fast = dummyHead;
        ListNode low = dummyHead;
        while(n > 0){
            fast = fast.next;
            n--;
        }
        //当fast在尾节点即fast.next为空时，low刚好在待删节点的前驱
        while(fast.next != null){
            fast = fast.next;
            low = low.next;
        }
        //删除low.next
        low.next = low.next.next;
        return dummyHead.next;
    }
}
